1. Field of the Invention
This invention relates to password analysis and modification. More specifically, it relates to analyzing password strength and developing strong passwords that are secure against efficient password cracking.
2. Description of the Prior Art
The use of passwords for protecting access is now ubiquitous in the Internet age, as Internet-based systems, such as online banking and online commerce, continue to rely heavily on passwords for authentication security. Human memorable passwords are thus a key element in the security of such systems. However, most users do not have the information to ensure that they are in fact using a “strong” password rather than one that can easily be broken. This limitation has led to the use and advocacy of password creation policies that purport to help the user in ensuring that the user chosen password is not easily breakable. The most prevalent password creation policy is the rule-based approach wherein users are given rules such as minimum length of eight characters and must contain an upper case letter and a special symbol. It has been shown by several authors that this approach by itself is not very effective (M. Weir, S. Aggarwal, M. Collins, and H. Stern, “Testing metrics for password creation policies by attacking large sets of revealed passwords,” Proceedings of the 17th ACM Conference on Computer and Communications Security (CCS '10); Oct. 4-8, 2010, pp. 163-175; E. R. Verheul, “Selecting secure passwords,” M. Abe (Ed.): CT-RSA 2007, LNCS 4377, pp. 49-66, 2007). A second type of password creation policy can be termed the random approach where an effectively random string is given by a system to the user. Clearly, the random approach has the problem that the given string is generally non-memorable, so the purpose of having a password that can easily be remembered is defeated.
A strong password is one that is difficult to guess or crack, yet users continue to employ weak passwords that can often be easily guessed or broken by available password cracking systems. Existing technology is mostly based on giving advice to users on how to create a “secure password.” Such advice is essentially a password creation policy, which advises users to follow rules while creating passwords. Suggested password creation rules include minimum length, use of upper case letters, lower case letters, and special symbols, including particular symbols. However, problems with these rules include inconsistencies within policies that are not based on a scientific approach, consequently resulting in a lack of strong passwords.
Moreover, current technologies tend to frustrate users when creating passwords because they do not allow users to utilize their normal password methods for choosing passwords. This leads to coping strategies, such as repeating a word just to make their passwords long enough to satisfy the policy requirements, which actually reduces password strength. Current restrictive policies are not user-friendly. These policies emphasize resistance to brute-force attacks, thus opening the password up to dictionary-based attack methods.
Existing technology also provides for password checkers that try to help users by providing a tool for them to check their password strength. These checkers propose to measure the strength of the proposed password based on certain parameters of the password. They check the password against some rules, give weights to the rules, and find an overall numeric value for the strength of the password. However, the rules used and weights given to the rules when applied to different parts of the proposed passwords are ad-hoc and have no scientific or empirical basis. These checkers do not define strength of a password based on evidence from real attacks, but define strength of a password generally based only on password structure, for example length of password, whether it can be found in the dictionary, etc.
Although not really an analysis of password strength, many studies attempt to determine various aspects of how users choose passwords. In Shannon Riley, “Password security: what users know and what they actually do,” Usability News, 8(1), 2006, Riley reports that in a study of 315 participants, about 75% of them reported that they have a set of predetermined passwords that they use frequently. Almost 60% reported that they do not change the complexity of their password depending on the nature of the website they use. In B. Stone-Gross, M. Cova, L. Cavallaro, B. Gilbert, M. Szydlowski, R. Kemmerer, C. Kruegel, and G. Vigna, “Your botnet is my botnet: Analysis of a botnet takeover,” Tech. Rep., April 2009, Stone-Gross et al. collected around 298 thousands passwords from the Torpig botnet. They found that almost 28% of users reused their passwords and they managed to crack over 40% of the passwords in less than 75 minutes. This illustrates that having strong passwords for less important websites such as social networking websites is likely to be as necessary as for websites such as online banking.
Most organizations and websites follow a rule-based approach in recommending or enforcing password policies. A study by Shay et al. (R. Shay, S. Komanduri, P. G. Kelley, P. G. Leon, M. L. Mazurek, L. Bauer, N. Christin, and L. F. Cranor, “Encountering stronger password requirements: user attitudes and behaviors,” In 6th Symposium on Usable Privacy and Security, July 2010) showed that users were not happy about changing the password creation policy to a stricter one and that it took on average 1.77 tries to create a new password accepted by the system based on a new password creation policy recently instituted. Riley (Shannon Riley, “Password security: what users know and what they actually do,” Usability News, 8(1), 2006) also reports that the average length of time users maintained their primary password was reported as 31 months and 52% of them never change their password at all.
Rule-based advice is confusing as there is no consistency across systems and websites in the requirements, with differing advice about length, number of symbols and digits, and even in the symbols that can be used. In Furnell, S., “An assessment of website password practices,” Computers & Security 26, 7-8 (2007), 445-451, it is shown that inconsistent and even contradictory recommendations make such advice unreliable for users. The U.S. NIST guideline (W. Burr, D. Dodson, R. Perlner, W. Polk, S. Gupta, E. Nabbus, “NIST special publication 800-63-1 electronic authentication guideline,” National Institute of Standards and Technology, Gaithersburg, Md., April, 2006), the basis for most rule-based policies, proposed a rule-based approach that used the notion of Shannon entropy for estimating password strength based on suggested values of the components of the password. However, Weir et al. (M. Weir, S. Aggarwal, M. Collins, and H. Stern, “Testing metrics for password creation policies by attacking large sets of revealed passwords,” Proceedings of the 17th ACM Conference on Computer and Communications Security (CCS '10), Oct. 4-8, 2010, pp. 163-175) performed password cracking attacks against multiple sets of real-life passwords and showed that the use of Shannon entropy as defined in MST is not an effective metric for gauging password strength and it does not give a sufficient model to decide on the strength of a given password.
Password expiration policies are designed to ensure stronger passwords over time. However, Zhang et al, (Y. Zhang, F. Monrose, and M, K. Reiter, “The security of modern password expiration: an algorithmic framework and empirical analysis,” In Proceedings of ACM CCS'10, 2010) showed that an attacker can easily get access to an account by capturing the account's previous passwords. They suggest that at least 41% of passwords can be broken offline from a previous password in a matter of seconds and only five online password guesses suffices to break 17% of accounts. A more recent study (Philip G. Inglesant, M. Angela Sasse, “The true cost of unusable password policies: password use in the wild,” Proc. of the 28th international conference on Human factors in computing systems, Apr. 10-15, 2010, Atlanta, Ga.) reports that although nowadays users understand the importance of secure behavior, they still find it too difficult to cope with password creation policies, and they rarely change their passwords due to the frustration of creating anew password along with the difficulty of memorizing it. In studies by Charoen et al. (Charoen, D., Raman, M., and Olfman, L., “Improving end user behavior in password utilization,” Systemic Practice and Action Research, 21(1), 55. 2008) and Adams and Sasse (A. Adams and M. A. Sasse, “Users are not the enemy,” Communications of the ACM, 42(12):40-46, 1999), it was found that users are not even unanimous about the necessity of having a strong password and the reason users choose insecure passwords is because they usually do not know how to create secure ones. Studies (J. Campbell, W. Ma, D. Kleeman, “Impact of restrictive composition policy on user password choices,” Behavior and information technology, Vol. 30, No. 3, May-June 2011) show that even restrictive password creation policies do not have impact on the use of meaningful information in passwords, nor does it reduces reusing the password. Reuse can subject users to other types of attacks such as phishing, key-logging and targeted attacks (Florencio, D. and Herley, C., “A large-scale study of web password habits,” In Proceeding of the 16th Int. Conf. on World Wide Web, 2007). A study by Shay et al. (R. Shay, S. Komanduri, P. G. Kelley, P. G. Leon, M. L. Mazurek, L. Bauer, N. Christin, L. F. Cranor, and S. Egelman, “Of passwords and people: measuring the effect of password-composition policies,” Proceeding of 2011 Annual Conference on Human Factors in Computing Systems, 2011) shows that the more restrictive and complicated the policy, the less user-friendly it is.
There have been some studies (G. Bard, “Spelling-error tolerant, order independent pass-phrases via the Damerau-Levenshtein string-edit distance metric,” Fifth Australasian Symposium on ACSW Frontiers—Volume 68 (Ballarat, Australia, Jan. 30-Feb. 2, 2007), 117-124; Yon, J. J., Blackwell, A., Anderson, R. and Grant A., “The memorability and security of passwords—some empirical results,” Technical Report No. 500 (September 2000) Computer Laboratory, University of Cambridge) exploring the use of the random password generation approach. The major problem is the usability of the password for the user since such a password has typically no context for the user and is naturally hard to remember. In A. Forget, S. Chiasson, P. C. van Oorschot, R. Biddle, “Improving text passwords through persuasion,” Symposium on Usable Privacy and Security (SOUPS) 2008, Jul. 23-25, 2008, Pittsburgh, Pa. USA, Forget et al. studied the memorability of passwords by randomly inserting or replacing fixed number of characters in a user chosen password. They showed that once the users confirmed their changed passwords, they could recall it as easily as the control group (passwords without change). However, they did not develop a methodology for analyzing the strength of these passwords.
Generating secure passwords is a tradeoff between creating a password that is hard to crack and usable. Some studies of passwords (Florencio, D. and Herley, C., “A large-scale study of web password habits,” In Proceeding of the 16th Int. Conf. on World Wide Web, 2007; Yan, J. J., Blackwell, A., Anderson, R. and Grant A., “The memorability and security of passwords—some empirical results,” Technical Report No. 500 (September 2000) Computer Laboratory, University of Cambridge) try to provide an understanding of how various policy factors make creating passwords easier, memorable, and usable, but none of them seem to have been applied in practice.
The work by Verheul (E. R. Verheul, “Selecting secure passwords,” M. Abe (Ed.): CT-RSA 2007, LNCS 4377, pp. 49-66, 2007) is an excellent example of trying to understand the relationship of various entropy measures in order to build better passwords. Verheul showed how to build reasonable short secure passwords based on calculating the Shannon entropy with assumptions on the min entropy and guessing entropy. However, there was no attempt in this paper to consider the usability or memorability of the passwords or how to modify a user suggested password.
The analyze-modify approach also has some related history. The analysis is usually a simple way to determine if a password is weak such as checking against a dictionary. In reality, this is not really a sufficient condition for a password to be strong. Current proactive password checkers generally follow such a blacklisting approach. See for example Yan (J. Yan, “A note on proactive password checking,” ACM New Security Paradigms Workshop, New Mexico, USA, 2001) and Spafford (E H Spafford, “OPUS: preventing weak password choices,” Computers & Security (1992)). However, simple blacklisting approaches generally have problems with any sophisticated dictionary based attack.
Perhaps the most relevant study is Schechter et al. (S. Schechter, C. Herley, M. Mitzenmacher, “Popularity is everything: a new approach to protecting passwords from statistical-guessing attacks”, HotSec'10: Proceedings of the 5th USENIX conference on Hot Topics in Security, 2010) in a study on popularity of passwords. They propose to build an oracle for existing passwords that are available to the Internet-scale authentication systems. They recommend that such popular passwords be disallowed and the main thrust of their work is to devise a way to efficiently store the large number of popular passwords that would be prohibited. An open question posed in their study is how to use the oracle without revealing the actual password to attackers while querying online. This study also runs across a storage problem. More recently, Castelluccia et al. (C. Castelluccia, M. Durmuth, D. Perito, “Adaptive password-strength meters from Markov models,” NDSS '12, 2012) explores measuring the strength of passwords using a Markov approach.
Weir et al. (M. Weir, S. Aggarwal, M. Collins, and H. Stern, “Testing metrics for password creation policies by attacking large sets of revealed passwords,” Proceedings of the 17th ACM Conference on Computer and Communications Security (CCS '10), Oct. 4-8, 2010, pp. 163-175) suggested that a probabilistic password attack system could be used to determine if a proposed password was weak and should be rejected. This probabilistic cracking system can be used for analyzing passwords. Once such an analysis is done, it can be shown how identified weak passwords can be effectively modified to be strong.
Accordingly, what is needed is a new password creation policy system that effectively analyzes password strength and modifies passwords in a manner that users can conveniently use the modified passwords. However, in view of the art considered as a whole at the time the present invention was made, it was not obvious to those of ordinary skill in the field of this invention how the shortcomings of the prior art could be overcome.
While certain aspects of conventional technologies have been discussed to facilitate disclosure of the invention, Applicants in no way disclaim these technical aspects, and it is contemplated that the claimed invention may encompass one or more of the conventional technical aspects discussed herein.
The present invention may address one or more of the problems and deficiencies of the prior art discussed above. However, it is contemplated that the invention may prove useful in addressing other problems and deficiencies in a number of technical areas. Therefore, the claimed invention should not necessarily be construed as limited to addressing any of the particular problems or deficiencies discussed herein.
In this specification, where a document, act or item of knowledge is referred to or discussed, this reference or discussion is not an admission that the document, act or item of knowledge or any combination thereof was at the priority date, publicly available, known to the public, part of common general knowledge, or otherwise constitutes prior art under the applicable statutory provisions; or is known to be relevant to an attempt to solve any problem with which this specification is concerned.